home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-02 / lysrc.zip / YACCLR0.PAS < prev    next >
Pascal/Delphi Source File  |  1993-01-24  |  3KB  |  107 lines
  1.  
  2. unit YaccLR0;
  3.  
  4. (* 2-16-91 AG *)
  5.  
  6. (* Copyright (c) 1990,91 by Albert Graef, Schillerstr. 18,
  7.    6509 Schornsheim/Germany
  8.    All rights reserved *)
  9.  
  10. interface
  11.  
  12. (* LR(0) set construction. For an explanation of this algorithm, see
  13.    Aho/Sethi/Ullman, "Compilers : Principles, Techniques and Tools,"
  14.    1986, Section 4.7. *)
  15.  
  16. procedure LR0Set;
  17.   (* constructs the LR(0) state set, shift and goto transitions and
  18.      corresponding kernel items *)
  19.  
  20. implementation
  21.  
  22. uses YaccBase, YaccTables;
  23.  
  24. (* This implementation is based on the algorithm given in Aho/Sethi/Ullman,
  25.    1986, Section 4.7. *)
  26.  
  27. procedure get_syms ( var item_set : ItemSet; var sym_set : IntSet );
  28.   (* get the symbols for which there are transitions in item_set *)
  29.   var i : Integer;
  30.   begin
  31.     with item_set do
  32.       begin
  33.         empty(sym_set);
  34.         for i := 1 to n_items do
  35.           with item[i], rule_table^[rule_no]^ do
  36.             if pos_no<=rhs_len then
  37.               include(sym_set, rhs_sym[pos_no]);
  38.       end;
  39.   end(*get_syms*);
  40.  
  41. function make_state ( var item_set : ItemSet; sym : Integer ) : Integer;
  42.   (* construct a new state for the transitions in item_set on symbol sym;
  43.      returns: the new state number *)
  44.   var i : Integer;
  45.   begin
  46.     with item_set do
  47.       begin
  48.         (* add the new state: *)
  49.         new_state;
  50.         for i := 1 to n_items do
  51.           with item[i], rule_table^[rule_no]^ do
  52.             if (pos_no<=rhs_len) and (rhs_sym[pos_no]=sym) then
  53.               add_item(rule_no, pos_no+1);
  54.         make_state := add_state;
  55.       end;
  56.   end(*make_state*);
  57.  
  58. procedure add_next_links;
  59.   (* add links to successor items for kernel items in the active state *)
  60.   var k, i : Integer;
  61.   begin
  62.     with state_table^[act_state] do
  63.       for k := trans_lo to trans_hi do
  64.         with trans_table^[k] do
  65.           for i := item_lo to item_hi do
  66.             with item_table^[i], rule_table^[rule_no]^ do
  67.               if (pos_no<=rhs_len) and (rhs_sym[pos_no]=sym) then
  68.                 next := find_item(next_state, rule_no, pos_no+1 );
  69.   end(*add_next_links*);
  70.  
  71. procedure LR0Set;
  72.   var act_items : ItemSet;
  73.       act_syms  : IntSet;
  74.       i         : Integer;
  75.   begin
  76.     (* initialize state 0: *)
  77.     new_state;
  78.     add_item(1, 1);  (* augmented start production *)
  79.     act_state := add_state;
  80.     (* build the state table: *)
  81.     repeat
  82.       (* compute the closure of the current state: *)
  83.       get_item_set(act_state, act_items);
  84.       closure(act_items);
  85.       (* sort items: *)
  86.       sort_item_set(act_items);
  87.       (* determine symbols used in shift and goto transitions: *)
  88.       get_syms(act_items, act_syms);
  89.       (* add transitions: *)
  90.       start_trans;
  91.       for i := 1 to size(act_syms) do
  92.         if act_syms[i]=0 then
  93.           (* accept action *)
  94.           add_trans(0, 0)
  95.         else
  96.           (* shift/goto action *)
  97.           add_trans(act_syms[i], make_state(act_items, act_syms[i]));
  98.       end_trans;
  99.       (* add next links to kernel items: *)
  100.       add_next_links;
  101.       (* switch to next state: *)
  102.       inc(act_state);
  103.     until act_state=n_states;
  104.   end(*LR0Set*);
  105.  
  106. end(*YaccLR0*).
  107.